package huaweiod.first;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 华为机试真题 Java 实现【星际篮球争霸赛】【100%通过率】【2022.11 Q4 新题】
 * LeetCode 698
 */
public class A_2023_29_MaxUnionBasketball {

    public static int maxUnionBasketball(int[] nums, int sum) {
        if (nums.length < 2) {
            return nums.length;
        }
        Arrays.sort(nums);
        for (int i = nums.length; i >= 1; i--) {
            if (sum % i == 0) {
                int[] path = new int[i];
                Arrays.fill(path, sum / i);
                if (dfs(nums.length - 1, nums, path)) {
                    return sum / i;
                }
            }
        }
        return sum;
    }

    public static boolean dfs(int index, int[] nums, int[] path) {
        if (index < 0) {
            return true;
        }
        for (int i = 0; i < path.length; i++) {
            if (i > 0 && path[i - 1] == path[i]) {
                continue;
            }
            if (nums[index] == path[i] || path[i] - nums[index] >= nums[0]) {
                path[i] -= nums[index];
                boolean dfs = dfs(index - 1, nums, path);
                if (dfs) {
                    return true;
                } else {
                    path[i] += nums[index];
                }
            }

        }
        return false;
    }

    public static void main(String[] args) {
        // 处理输入
        Scanner in = new Scanner(System.in);
        String param_str = in.nextLine();
        int count = Integer.valueOf(param_str);

        //构造输入数据结构,并求和
        int[] nums = new int[count];
        String num_str = in.nextLine();
        int sum = 0;
        String[] num_list = num_str.split(" ");
        for (int i = 0; i < count; i++) {
            nums[i] = Integer.valueOf(num_list[i]);
            sum += Integer.valueOf(num_list[i]);
        }
        // process
        System.out.println(maxUnionBasketball(nums, sum));
    }
}
